/**
 * \file heap.hpp
 * \brief Heap class
 * \author Wouter Caarls <w.caarls@tudelft.nl> 
 *
 * \verbatim
 * Copyright (c) 2005-7 Wouter Caarls, Delft University of Technology
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * \endverbatim
 */

#ifndef __HEAP_HPP
#define __HEAP_HPP

#include <iostream>
#include <stdlib.h>

/// Heap data type
template<class T>
class CHeap
{
  public:
    CHeap(int _size) : m_len(0)
    {
      // Find proper heap size which can accomodate desired size
      m_size = 1;
      while (m_size < _size) m_size = (m_size+1)*2-1;

      m_data = new T[m_size];

      // 1-base math is easier -- decrement data pointer
      m_data--;
    }

    ~CHeap()
    {
      // Increment data pointer before freeing
      m_data++;

      delete[] m_data;
    }

    /// Add an element to the heap
    inline void insert(T &obj)
    {
      if (m_len < m_size)
      {
	// Add; heap is filled from the left.
	m_data[++m_len] = obj;

	// Percolate upwards.
	swapup(m_len);
      }
      else
	throw "Heap full";
    }

    /// Return the element at the top of the heap
    inline T top()
    {
      if (m_len)
	return m_data[1];
      else
	throw "Empty heap";
    }
 
    /// Return and remove the element at the top of the heap
    inline T pop()
    {
      if (m_len)
      {
	// Remember top
	T temp = m_data[1];

	// Replace last element at the top
	m_data[1] = m_data[m_len--];

	// Percolate downwards
	swapdown(1);

	return temp;   
      }
      else
	throw "Empty heap";
    }

    /// Print the heap
    void print(void)
    {
      for (int ii=1; ii <= m_len; ii++)
        std::cout << m_data[ii] << std::endl;
      std::cout << std::endl;
    }

    /// Return the of elements the heap can store
    inline int size() { return m_size; };

    /// Return the current size of the heap
    inline int len()  { return m_len; };

  protected:
    /// Swap two heap elements
    inline void swap(int i1, int i2)
    {
      T temp;

      temp = m_data[i1];
      m_data[i1] = m_data[i2];
      m_data[i2] = temp;
    }

    /// If heap element is smaller than its parent, swap and recurse upwards.
    void swapup(int i)
    {
      if (i>1)
      {
        if (m_data[i] < m_data[i/2])
        {
          swap(i, i/2);
          swapup(i/2);
        }
      }
    }
  
    /// If a heap element is greater than one of its children, swap it with
    /// the smallest and recurse downwards
    void swapdown(int i)
    {
      if ((i*2+1 <= m_len))
      {
	// We have two children
	if (m_data[i*2] < m_data[i*2+1])
	{
	  // Left neighbour is smallest
	  if (m_data[i] > m_data[i*2])
	  {
	    swap(i, i*2);
	    swapdown(i*2);
	  }
	}
	else
	{
	  // Right neighbour is smallest
	  if (m_data[i] > m_data[i*2+1])
	  {
	    swap(i, i*2+1);
	    swapdown(i*2+1);
	  }
	}
      }
      else if (i*2 <= m_len)
      {
	// Only one child
	if (m_data[i] > m_data[i*2])
	{
	  swap(i, i*2);
	  swapdown(i*2);
	}
      }
    }
  
  protected:
  int m_size,  ///< Number of elements the heap can store.
      m_len;   ///< Current size of the ehap
  T   *m_data; ///< Heap data storage; 1-based.
};

#endif /* __HEAP_HPP */

